""" Code example from Complexity and Computation, a book about
exploring complexity science with Python.  Available free from

http://greenteapress.com/complexity

Copyright 2011 Allen B. Downey.
Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
"""

class Vertex(object):
    """A Vertex is a node in a graph."""

    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        """Returns a string representation of this object that can
        be evaluated as a Python expression."""
        return 'Vertex(%s)' % repr(self.label)

    __str__ = __repr__
    """The str and repr forms of this object are the same."""


class Edge(tuple):
    """An Edge is a list of two vertices."""

    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError('Edges must connect exactly two vertices.')
        return tuple.__new__(cls, vs)

    def __repr__(self):
        """Return a string representation of this object that can
        be evaluated as a Python expression."""
        return 'Edge(%s, %s)' % (repr(self[0]), repr(self[1]))

    __str__ = __repr__
    """The str and repr forms of this object are the same."""


class Graph(dict):
    """A Graph is a dictionary of dictionaries.  The outer
    dictionary maps from a vertex to an inner dictionary.
    The inner dictionary maps from other vertices to edges.
    
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs=[], es=[]):
        """Creates a new graph.  
        vs: list of vertices;
        es: list of edges.
        """
        for v in vs:
            self.add_vertex(v)
            
        for e in es:
            self.add_edge(e)

    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions.

        If there is already an edge connecting these Vertices, the
        new edge replaces it.
        """
        v, w = e
        self[v][w] = e
        self[w][v] = e

    def get_edge(self, v, w):
        """If there is an edge connecting v and w, return it, else return None.
        """
        return self[v].get(w, None)

    def remove_edge(self, e):
        """remove an edge from graph.
        """
        v, w = e
        del self[v][w]
        del self[w][v]

    def vertices(self):
        """return list of vertices in graph.
        """
        return self.keys()

    def edges(self):
        """return list of edges.
        """
        return list(set(reduce(lambda x, y: self[x].values() + self[y].values(), self.keys())))

    def out_vertices(self, v):
        """return list of ajacent vertices.
        """
        return self[v].keys()

    def out_edges(self, v):
        """return list of edges which take v as its end.
        """
        return self[v].values()

    def add_all_edges(self):
        """add all edges to an graph without any edge.
        """
        for v in self.keys():
            for w in self.keys():
                if v == w:
                    continue
                if w in self[v]:
                    continue
                self.add_edge(Edge(v, w))

    def add_regular_edges(self, n):
        """add regular edges to an graph without any edge.
        """
        m = len(self)
        if (m * n) % 2 != 0:
            print("Invalid order: %d" % n)
            return False

        for v in self:
            rest = n - len(self[v])
            if rest == 0:
                continue

            cands = []
            for k in self:
                if k == v or len(self[k]) == n:
                    continue
                cands.append(k)

            cands.sort(key=lambda x: len(self[x]))
            for x in cands[:rest]:
                self.add_edge(Edge(v, x))

        return True

    def is_connected(self):
        """ determine if a graph is connected.
        """

        vertices = {i:0 for i in self}
        q = []
        first = tuple(vertices.keys())[0]
        q.append(first)
        vertices[first] = 1
        while q:
            i = q.pop()
            for v in self[i]:
                if not vertices[v]:
                    q.append(v)
                    vertices[v] = 1
        return sum(vertices.values()) == len(self)



def main(script, *args):
    pass
    #v = Vertex('v')
    #print v
    #w = Vertex('w')
    #print w
    #e = Edge(v, w)
    #print e
    #g = Graph([v,w], [e])
    #print g


if __name__ == '__main__':
    import sys
    main(*sys.argv)
